package main

/*
给定一个二叉树的根节点 root，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
*/
func main() {
	node1 := &TreeNode{12, nil, nil}
	node1.Left = &TreeNode{9, nil, nil}
	node1.Right = &TreeNode{20, nil, nil}
	node1.Right.Left = &TreeNode{15, nil, nil}
	node1.Right.Right = &TreeNode{7, nil, nil}

	println(pathSum(node1, 12))

}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
 *	pathSum
 *	@Description: 递归 深度优先
 *	@param root *TreeNode
 *	@param targetSum int
 *	@return count int
 */
func pathSum(root *TreeNode, targetSum int) (count int) {

	if root == nil {
		return
	}

	count = recursive(root, targetSum)
	count += pathSum(root.Left, targetSum)
	count += pathSum(root.Right, targetSum)

	return count

}

/**
 *	recursive
 *	@Description: 递归 深度优先
 *	@param root *TreeNode
 *	@param targetSum int
 *	@return sum int
 */
func recursive(root *TreeNode, targetSum int) (sum int) {

	if root == nil {
		return
	}
	val := root.Val
	if val == targetSum {
		sum++
	}
	sum += recursive(root.Left, targetSum-val)
	sum += recursive(root.Right, targetSum-val)
	return
}
